package leetcode.dynamic_programming;

/**
 * @author mgl
 * @version 1.0
 * @description TODO 斐波那契数列，动态规划算法求解
 * @date 2023/9/23 10:26
 */
public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(new Fibonacci().fib(5));
    }

    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int[] a = new int[n + 1];
        a[1] = 1;
        a[2] = 1;

        for (int i = 3; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }

        return a[n];
    }

    public int fib02(int n) {
        int[] a = new int[n + 1];
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        a[0] = 0;
        a[1] = 1;
        a[2] = 1;
        for (int i = 3; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2] + a[i - 3];
        }

        return a[n];
    }
}
